#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef enum { false, true } bool;

double Random(double a, double b) {
    /* 生成 [a,b] 区间内的随机数 */
    double t;

    t = (double)rand() / RAND_MAX; /* 生成 [0,1] 区间内的随机数 */
    return (a + t * (b - a));
}

int PowMod(int a, int i, int n) {
    int x, y;

    if (i == 0) {
        return 1; /* a^0 mod n = 1 */
    }
    x = PowMod(a, i >> 1, n); /* 计算 a^{i/2} mod n */
    if (x == 0) {
        return 0; /* 若x为0，则n非素数，退出递归 */
    }
    y = (x * x) % n; /* 计算 (a^{i/2} mod n)*(a^{i/2} mod n) mod n */
    if (y == 1 && x != 1 && x != (n - 1)) { /* 违反二次探测定理，退出 */
        return 0;
    }
    if (i % 2 == 1) { /* 若i为奇数，再多乘一次a */
        y = (y * a) % n;
    }
    return y;
}

/* 算法16-8：Miller-Rabin素数测试算法 MillerRabin_IsPrime(n, k) */
bool MillerRabin_IsPrime(int n, int k) {
    int a, i;

    if (n == 2) {
        return true;
    }
    if (n < 2 || n % 2 == 0) {
        return false;
    }
    srand((unsigned)time(NULL)); /* 为随机数产生种子 */
    for (i = 0; i < k; i++) { /* 进行k次测试 */
        a = (int)Random(2, n - 1); /* 选取2到n-1间的随机数a */
        if (PowMod(a, n - 1, n) != 1) { /* 计算 a^{n-1} mod n */
            return false;
        }
    }
    return true;
}
/* 算法16-8 结束 */

int main(void) {
    int n, k;

    scanf("%d %d", &n, &k);
    printf("%d", MillerRabin_IsPrime(n, k));

    return 0;
}